// 给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。

// 字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。

// 说明：

// 字母异位词指字母相同，但排列不同的字符串。   <----这个条件在这题一点意义都没有。。。。
// 不考虑答案输出的顺序。


//滑动窗口+双指针解法

// 用双指针来表示滑动窗口的两侧边界，当滑动窗口的长度等于p的长度时，表示找到一个异位词，两种方式的时间复杂度都是O(n)级别的
// 先说结论，Python用数组更快一点点（差不太多其实），Java用双指针更快一点，下面是具体步骤：

// 定义滑动窗口的左右两个指针left，right
// right一步一步向右走遍历s字符串
// right当前遍历到的字符加入s_cnt后不满足p_cnt的字符数量要求，将滑动窗口左侧字符不断弹出，也就是left不断右移，直到符合要求为止。
// 当滑动窗口的长度等于p的长度时，这时的s子字符串就是p的异位词。
// 其中，left和right表示滑动窗口在字符串s中的索引，cur_left和cur_right表示字符串s中索引为left和right的字符在数组中的索引
class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int m = s.length();
        int n = p.length();
        int[] pnt = new int[26];
        int[] snt = new int[26];
        List<Integer> res = new ArrayList<>();
        if(n>m)
            return res;
        for(int i =0;i<n;i++)
        {
            pnt[p.charAt(i)-'a']++;
        }
        int left = 0;
        int right = 0;
        while(right<m)
        {
            int k =s.charAt(right)-'a';
            snt[k]++;
            while(snt[k]>pnt[k])
            {
                snt[s.charAt(left)-'a']--;
                left++;
            }
            if(right-left+1 == n)
            {
                res.add(left);
            }
            right++;
        }
        return res;
    }
}